package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:统计1的个数
 * 题目详细链接
 * https://www.cnblogs.com/du001011/p/16963957.html
 * author: Mr.Du
 * Date: 2022/12/7
 * Time: 18:27
 */
public class CountBits {
    
    // 方法一
    public int[] countBits(int n) {
        int[] nums = new int[n + 1];
        for(int i = 0;i < nums.length;i++){
            int count = 0;
            // 统计每个数二进制中1的个数
            // 右移并与1相与，等于1就加1
            for(int j = 0;j < 32;j++){
                if(((i >> j) & 1) == 1){
                    count++;
                }
            }
            // 赋值
            nums[i] = count;
        }
        return nums;
    }
    
    // 方法二
    public int[] countBits1(int n) {
        int[] nums = new int[n + 1];
        for(int i = 0;i < nums.length;i++){
            if(nums[i] % 2 == 0){
                nums[i] = nums[i / 2];
            }else{
                nums[i] = nums[i-1] + 1;
            }
        }
        return nums;
    }
    
    // 方法三(方法二的优化)
    public int[] countBits2(int n) {
        int[] nums = new int[n + 1];
        for(int i = 0;i < nums.length;i++){
            nums[i] = nums[i >> 1] + (i & 1);
        }
        return nums;
    }
}
